﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_31_NextPermutation
{
    class MainProject
    {
        static void Main(string[] args)
        {
            int[] array = new int[]
            {
            1,3,2
            };
            NextPermutation(array);
            Console.WriteLine();
            //Console.WriteLine(IsPalindrome(1000021));
            Console.ReadKey();
        }
        public static void NextPermutation(int[] nums)
        {
            if (nums.Length == 1) return;
            if (nums.Length==2)
            {
                Array.Reverse(nums);
                return;
            }
            int firstIndex = -1;
            int secondIndex = 0;

            int recordIndex_1 = 0;
            int recordIndex_2 = 0;
            int minValue = int.MaxValue;
            for (int i = nums.Length - 2; i >= 0; i--)
            {
                firstIndex = i;
                secondIndex = firstIndex + 1;
                minValue = int.MaxValue;
                bool isBreak = false;
                while (secondIndex <= nums.Length - 1)
                {
                    int val = nums[secondIndex] - nums[firstIndex];
                    if (val>0)
                    {
                        minValue = Math.Min(val, minValue);
                        recordIndex_1 = firstIndex;
                        recordIndex_2 = secondIndex;
                        isBreak = true;
                    }
                    secondIndex++;
                }

                if (isBreak) break;
            }
            if (minValue == int.MaxValue)
            {
                Array.Sort(nums);
            }
            else
            {
                int temp = nums[recordIndex_1];
                nums[recordIndex_1] = nums[recordIndex_2];
                nums[recordIndex_2] = temp;
                int first = recordIndex_1 + 1;
                int second = nums.Length;
                Array.Sort(nums, first, second- first);
            }
        }
    }
}
